/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iii
@Language: C++
@Datetime: 16-02-09 05:43
*/

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        // write your code here
        if (prices.size()<2)
            return 0;
        vector<int> left,right;
        for(int i=prices.size();i;--i){
            left.push_back(0);
            right.push_back(0);
        }
        int min=prices[0];
        for(int i=1;i<prices.size();++i){
            min = (min < prices[i]?min:prices[i]);
            left[i]=(left[i-1]>prices[i]-min?left[i-1]:prices[i]-min);
        }
        int max=prices[prices.size()-1];
        for(int i=prices.size()-2;i>=0;--i){
            max = (max>prices[i]?max:prices[i]);
            right[i] = (right[i+1]>max-prices[i]?right[i+1]:max-prices[i]);
        }
        max = 0;
        for(int i=left.size()-1;i>=0;--i)
            max = (max>left[i]+right[i]?max:left[i]+right[i]);
        return max;
    }
};